1. Technical Field
The invention relates to data compression. More particularly, the invention relates to a novel data compression technique referred to as zero-search, zero-memory vector quantization.
2. Description of the Prior Art
The subject of this invention is a new technique for data compression, referred to herein as zero-search, zero-memory vector quantization. Vector quantization is a well-known and widely practiced method of lossy data compression. By “data compression” is meant that some body of digital data, typically a sequence of vectors of some fixed dimension, and requiring some amount of memory (for storage) or communication bandwidth (for transmission), is converted into a smaller amount of digital data. From this converted representation, usually referred to as the compressed form of the data, a reasonable facsimile of the original body of data may be reconstructed, via an appropriate decompression algorithm. Because data reconstructed by this method may not exactly match the original, the scheme is said to be lossy. By contrast, a compression scheme with the property that the original data may always be exactly reconstructed from its compressed representation is said to be lossless.
Vector quantization operates by establishing a small set of vectors, called a codebook, which are representative of those that will be processed by the deployed system. When a vector is presented for compression, a computation determines the codebook entry that is closest to it, and the index of this entry within the codebook, rather than the vector itself, is transmitted (or stored) as a proxy of the input. Upon receipt (or readback) of index i, the input data are reconstructed by extracting the i th entry from the codebook, and presenting this vector as a facsimile of the original. Though it can achieve very high rates of compression, two significant drawbacks of this method are:
(1) The need to store the codebook (if the system is being used for data transmission, this must be done at both the sender and the receiver), and
(2) The need for the sender to search the codebook, to find the closest match to the input vector.